package sword.T47;

/**
 * @Author: 18362
 * @Create: 2022-04-09 18:10:44 星期六
 */

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        for (int i=0; i<m; ++i) {
            if (i == 0) {
                dp[0] = grid[0][0];
                for (int j=1; j<n; ++j)
                    dp[j] = dp[j-1] + grid[0][j];
            } else {
                dp[0] += grid[i][0];
                for (int j=1; j<n; ++j) {
                    dp[j] = Math.max(dp[j-1], dp[j]) + grid[i][j];
                }
            }
        }
        return dp[n-1];
    }
}